#include "mergesort.h"
#include <stdlib.h>
static void swap(int array[], int i, int j)
{
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
}
static void merge(int src[],int des[],int low, int mid, int high)
{
        int i = low;
        int j = mid + 1;
        int k  = low;
        while ((i <= mid) && (j <= high)){//将小的放到目的地中
                if(src[i] < src[j]){
                        des[k++] = src[i++];
                }else {
                        des[k++] = src[j++];
                }
        }
        while (i <= mid){ //若还剩几个尾部元素
                des[k++] = src[i++];
        }
        while (j <= high){ //若还剩几个尾部元素
                des[k++] = src[j++];
        }
}
//每次分为两路 当只剩下一个元素时,就不需要在划分
static void MSort(int src[],int des[],int low, int high, int max)
{
        if(low == high){//只有一个元素,不需要归并,结果赋给des[low]
                des[low] = src[low];
        }else{
                int mid = (low+high)/2;
                int* space = (int*)malloc(sizeof(int)*max);
                //递归进行两路划分
                //当剩下一个元素时,递归划分结束,然后开始merge归并操作
                if(space !=NULL){
                        MSort(src,space,low,mid,max);
                        MSort(src,space,mid+1,high,max);
                        merge(space,des,low,mid,high);
                }
                free(space);
        }
} 
void mergeSort(int array[], int len)
{
        MSort(array,array,0,len-1,len);
}